// @algorithm @lc id=4 lang=cpp
// @title median-of-two-sorted-arrays

#include <iostream>
#include <vector>
#include <string>
#include "algm/algm.h"
using namespace std;
// @test([1,3],[2])=2.00000
// @test([1,2],[3,4])=2.50000
// @test([1,2,3,7,9],[2,4,8,10])=4.00000
// @test([1,2,3,7,9],[1,2,3,7,9])=3.00000
// @test([1],[1])=1.00000
// @test([1,2,3],[0])=1.50000
// @test([0],[1,2,3])=1.50000
// @test([1,2,3],[])=2.00000
// @test([],[1,2,3])=2.00000

/**
 * @brief
 * 这种类型的问题其实就是在两个数组中寻找第K小的问题.
 * 参考了题解https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/中的解法3
 * 题目要求如果是O(m+n), 那么归并算法就可以做, 但是要求O(log(m+n))时, 算法经常使用二分思想进行优化.
 * 可以在两个数组AB中各取前k/2个元素, 就会发生两种情况:
 * 1. A数组的第k/2个元素小于(或者等于)B数组的第k/2个元素, 那么说明第K小的数一定在B数组里, 那么A数组就可以去掉这k/2个元素后再与B数组结合, 寻找剩下的第m小的数(m为k减去A数组去掉元素的数量).
 * 2. B数组的第k/2个元素小于(或者等于)A数组的第k/2个元素, 与上同理.
 * 这样k的值一直缩小, 直到下面这种情况时结果被找到:
 * 1. k=1时, 那么两个数组此时第一个元素, 谁小谁就是结果.
 * 2. 某个数组已经为空时, 结果就是另一个数组的第k小的元素.
 *
 * 有一个很巧妙的思考是,
 * 我们都知道一个偶数长度的数组A的中位数可以是(A[(len - 1) / 2]+ A[len/ 2]) / 2,
 * 一个奇数长度的数组A的中位数其实也可以是(A[(len - 1) / 2]+ A[len/ 2]) / 2, 因为(len - 1) / 2 = len/ 2
 * 这可以帮助我们合并数组的总长度是奇数和偶数的情况
 */
class Solution {
public:
    double getKth(vector<int>& nums1, vector<int>& nums2, int l1, int len1, int l2, int len2, int k)
    {
        if (len2 < len1)
            return getKth(nums2, nums1, l2, len2, l1, len1, k); // 让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1空了
        if (len1 == 0)
            return nums2[l2 + k - 1];
        if (k == 1)
            return nums1[l1] < nums2[l2] ? nums1[l1] : nums2[l2];

        int r1 = l1 + (len1 < k / 2 ? len1 : k / 2) - 1;
        int r2 = l2 + (len2 < k / 2 ? len2 : k / 2) - 1;

        if (nums1[r1] < nums2[r2]) {
            return getKth(nums1, nums2, r1 + 1, len1 - (r1 - l1 + 1), l2, len2, k - (r1 - l1 + 1));
        } else {
            return getKth(nums1, nums2, l1, len1, r2 + 1, len2 - (r2 - l2 + 1), k - (r2 - l2 + 1));
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int len1 = nums1.size();
        int len2 = nums2.size();

        //合并将偶数和奇数的情况合并, 比如[len1 + len2 = 6]时, 我们就是求第3和第4小的数, [len1 + len2 = 7]时, 我们就是求第四小的数
        int left  = (len1 + len2 + 1) / 2;
        int right = (len1 + len2 + 2) / 2;

        return (getKth(nums1, nums2, 0, len1, 0, len2, left) + getKth(nums1, nums2, 0, len1, 0, len2, right)) * 0.5;
    }
};